package company;

import java.util.*;

/**
 * 127 单词接龙 还是超时了 这个解法学会了记录每个分支的路径
 * 按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：
 * <p>
 * 每对相邻的单词之间仅有单个字母不同。
 * 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
 * sk == endWord
 * 给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
 * 输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
 * 解释：存在 2 种最短的转换序列：
 * "hit" -> "hot" -> "dot" -> "dog" -> "cog"
 * "hit" -> "hot" -> "lot" -> "log" -> "cog"
 * 示例 2：
 * <p>
 * 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
 * 输出：[]
 * 解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。
 */
public class FindLaddersTwo127 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String beginWords = sc.nextLine();
        String endWords = sc.nextLine();
        String[] split = sc.nextLine().split(",");
        List<String> wordIdList = new ArrayList<>(Arrays.asList(split));
        List<List<String>> ladders = findLadders(beginWords, endWords, wordIdList);
        for (List<String> list : ladders){
            for (String word: list) {
                System.out.print(word+"->");
            }
            System.out.println();
        }
    }

    public static List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        // 定义队列
        Deque<List<String>> qu = new LinkedList();
        Set<String> wordId = new HashSet<>(wordList);
        List<List<String>> res = new ArrayList<>();
        if (!wordId.contains(endWord)) {
            return res;
        }
        wordId.remove(beginWord);

        // 队列访问
        List<String> path = new ArrayList<>();
        path.add(beginWord);
        qu.offer(path);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        boolean isFound = false;
        // 每个单词需要经过转换
        while (!qu.isEmpty()) {
            int currentSize = qu.size();
            Set<String> subVisited = new HashSet<>();
            // 处理每一层
            for (int i = 0; i < currentSize; i++) {
                List<String> currPath = qu.poll();
                String currWord = currPath.get(currPath.size() - 1);
                // 获取当前单词的邻居节点
                List<String> negeightList = getNegeight(currWord, wordId);

                // 有2个（包含两个）以上的同一层的，这时候就开始从循环产生两条以上的路径
                for (String negeigth : negeightList) {
                    if (!visited.contains(negeigth)) {
                        if (negeigth.equals(endWord)) {
                            isFound = true;
                            currPath.add(negeigth);

                            // new一个新的列表，是每条路径都是独立的
                            res.add(new ArrayList<>(currPath));

                            // 移除掉新添加的，是为了不影响邻居节点的路径
                            currPath.remove(currPath.size() - 1);
                        } else {
                            currPath.add(negeigth);
                            qu.offer(new ArrayList<>(currPath));
                            currPath.remove(currPath.size() - 1);
                            subVisited.add(negeigth);
                        }
                    }
                }
            }
            visited.addAll(subVisited);
            // 每一层同时遍历，如果在这一层找到了结尾点，那么路径就是最短的，可以退出了
            if (isFound) {
                return res;
            }
        }
        return res;
    }


    // 求所有邻居节点
    public static List<String> getNegeight(String currWord, Set<String> wordId) {
        int len = currWord.length();
        char[] chars = currWord.toCharArray();
        List<String> list = new ArrayList<>();
        for (char k = 'a'; k <= 'z'; k++) {
            for (int i = 0; i < len; i++) {
                char tmp = chars[i];
                if (tmp == k) {
                    continue;
                }
                chars[i] = k;
                String newWord = String.valueOf(chars);
                if (wordId.contains(newWord)) {
                    list.add(newWord);
                }
                chars[i] = tmp;
            }
        }
        return list;
    }
}
